1. Field of the Invention
The present invention relates to spelling correction algorithms, including methods for identifying alternative spellings of search strings submitted to a search engine.
2. Description of the Related Art
Many World Wide Web sites and online services provide search engine systems (“search engines”) for assisting users in locating items of interest. For example, a number of web sites provide Internet search engines for locating web pages and other types of Internet content, and online services such as LexisNexis and Westlaw provide search engines for locating articles, court opinions, and other types of publications. In addition, online merchants commonly provide search engines for assisting users in locating products and other types of items represented in an electronic catalog.
To perform a search using a text-based search engine, a user submits a search query which contains or consists of a search string. The search string may consist of a single search term (e.g., “Olympics”) or multiple search terms (e.g., “Olympic marathon”). Other types of elements, such as search field identifiers and logical operators, may also be included in a search query. A query server of the search engine processes the search query to identify any items that match the search string. The set of items (web pages, news articles, products, etc.) identified by the query server program is referred to as the “search result set,” and is presented to the user as a list of located items. In Web-based implementations, the search result set is typically presented to the user as a hypertextual listing of the located items.
When the user of a search engine misspells a term in a search string by mistyping or failing to remember the term, the misspelled term commonly will not match any of the database terms encompassed by the search, or will match a database term that the user did not intend. Thus, the search engine may return a null (empty) search result, or a search result set containing few, if any, of the items that are relevant to the user's objective. To reduce this problem, some search engines suggest alternative strings that are similar in spelling to the user-entered search string. Frequently, however, these alternative search strings do not represent the user's intent, or otherwise are not helpful to the user.